package com.demo.java.OD151_200.OD173;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【招聘】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145793442
 */
public class OdMain {
    public static void main(String[] args) {
        try (Scanner s = new Scanner(System.in)) {
            // 输入面试次数和面试官的数量限制
            int m = s.nextInt(), n = s.nextInt();
            int[][] arr = new int[n][2];

            // 输入每个面试的开始和结束时间
            for (int i = 0; i < n; i++)
                arr[i] = new int[]{s.nextInt(), s.nextInt()};

            // 按照开始时间进行排序
            Arrays.sort(arr, Comparator.comparingInt(c1 -> c1[0]));

            // 双端队列用于存储面试官的工作状态
            Deque<int[]> deque = new ArrayDeque<>();
            // 初始化第一个面试
            deque.offer(new int[]{arr[0][1], 1});

            // 遍历所有面试，安排面试官
            for (int i = 1; i < n; ++i) {
                boolean flag = false;

                // 检查是否可以使用现有面试官
                for (int[] p : deque) {
                    if (p[0] <= arr[i][0] && p[1] < m) { // 面试官空闲且没有达到最大数量
                        p[1]++;
                        p[0] = arr[i][1]; // 更新面试官结束时间
                        flag = true;
                        break;
                    }
                }

                // 如果没有可用面试官，则需要增加一个新的面试官
                if (!flag) deque.offer(new int[]{arr[i][1], 1});
            }

            // 输出需要的最少面试官数量
            System.out.print(deque.size());
        }
    }
}